package com.mamingchao.basic.swardToOffer;

import java.util.Stack;

/**
 * 请编写一个程序,对一个栈里的整型数据,按升序进行排序(即排序前,栈里
 * 的数据是无序的,排序后最大元素位于栈顶),要求最多只能使用一个额外的
 * 栈存放临时数据,但不得将元素复制到别的数据结构中。
 */
public class SortStack {

    public static void main(String[] args) {
        Stack<Integer> originalStack = new Stack<>();
        originalStack.push(1);
        originalStack.push(7);
        originalStack.push(5);
        originalStack.push(2);
        originalStack.push(3);
        originalStack.push(8);

        Stack<Integer> sortedStackByAscOrder = sortStackByAscOrder(originalStack);

        while (!sortedStackByAscOrder.empty()) {
            System.out.println(sortedStackByAscOrder.pop());
        }
    }


    private static Stack sortStackByAscOrder(Stack<Integer> originalStack){
        Stack<Integer> standBy = new Stack<>();

        while (!originalStack.empty()) {
            // 取出来原栈 最上层的元素
            int cur = originalStack.pop();
            // 如果辅助栈 是空的，直接放进
            if (standBy.empty()) {
                standBy.push(cur);
            } else {
                // 如果辅助栈不是空的
                int topOneInStandBy = standBy.peek();
                // 如果比辅助栈最上面的小，则把辅助栈最上面的挪回 原始栈
                while (!standBy.empty() && cur < topOneInStandBy) {
                    originalStack.push(standBy.pop());
                }
                standBy.push(cur);

            }
        }
        return standBy;
    }
}
